package algorithms;

/**
 * 动态规划
 * 最优子结构
 * <p>
 * 序列X_m与序列Y_n，定义Z_k是两个序列X_m和Y_n的任意一个LCS。（这个定义一定是有效的）
 * 定理：
 * 如果x(m)=y(n)，那么z(k)=x(m)=y(n),且Z_(k-1)是X_(m-1)和Y_(n-1)的LCS；
 * 如果x(m)!=y(n)，那么 如果z(k)!=x(m)，则Z_k是序列X_(m-1)和序列Y_n的LCS；
 * 如果x(m)!=y(n)，那么 如果z(k)!=y(n)，则Z_k是序列X_m和序列Y_(n-1)的LCS；
 * <p>
 * x(m)!=y(n) 说明x(m)和y(n)不会同时是z(k)，即 z(k)=x(m) and z(k)=y(n) 是假的，
 * 因此!(z(k)=x(m) and z(k)=y(n)) <=> z(k)!=x(m) or z(k)!=y(n) 是真的，
 * 也就是定理中的后面两步的由来。
 * <p>
 * 序列X_m和Y_n可以有多个LCS，但是按照下面的算法只能求出其中一个，因为我们不知道上面定理中的z(k)，
 * 只能求定理后两种情况的max(LCS,LCS)，这个max是一个比较的过程，也是不断筛选不同LCS的过程。
 */
public class 最长公共子序列 {
    public static void main(String[] args) {
        String x = "abcbdab";
        String y = "bdcaba";

        System.out.println(dpLCS(x, y));
        System.out.println(lcs(x, y));
    }

    /**
     * 下面的算法仅仅是利用了分治的算法，还没有成功利用动态规划。
     *
     * @param x
     * @param y
     * @return
     */
    private static String lcs(String x, String y) {
        if (x.length() == 0 || y.length() == 0) {
            return "";
        }

        if (x.charAt(x.length() - 1) == y.charAt(y.length() - 1)) {
            return lcs(x.substring(0, x.length() - 1), y.substring(0, y.length() - 1)) + x.charAt(x.length() - 1);
        }

        String x_1 = lcs(x.substring(0, x.length() - 1), y);
        String y_1 = lcs(x, y.substring(0, y.length() - 1));

        if (y_1.length() >= x_1.length()) {
            return y_1;
        } else {
            return x_1;
        }
    }

    /**
     * 动态规划的特点：子问题重叠
     * 从问题的描述来看，如果知道子问题的长度，那么父问题的长度也就可以知道了。
     * 那么就先从最小的问题的开始计算，然后存储到表格中，后面的父问题就可以直接使用前面存储的表格结果。
     *
     * @param x
     * @param y
     * @return
     */
    private static int dpLCS(String x, String y) {
        int[][] dp = new int[x.length() + 1][y.length() + 1];

        for (int row = 0; row < x.length() + 1; row++) {
            dp[row][0] = 0;
        }
        for (int column = 0; column < y.length() + 1; column++) {
            dp[0][column] = 0;
        }

        for (int row = 1; row < x.length() + 1; row++) {
            for (int column = 1; column < y.length() + 1; column++) {
                if (x.charAt(row - 1) == y.charAt(column - 1)) {
                    dp[row][column] = dp[row - 1][column - 1] + 1;
                } else {
                    dp[row][column] = Math.max(dp[row - 1][column], dp[row][column - 1]);
                }
            }
        }

        return dp[x.length()][y.length()];
    }
}
